// dibview.cpp : implementation of the CDibView class
//
// This is a part of the Microsoft Foundation Classes C++ library.
// Copyright (C) 1992-1998 Microsoft Corporation
// All rights reserved.
//
// This source code is only intended as a supplement to the
// Microsoft Foundation Classes Reference and related
// electronic documentation provided with the library.
// See these sources for detailed information regarding the
// Microsoft Foundation Classes product.

#include "stdafx.h"
#include "diblook.h"

#include "dibdoc.h"
#include "dibview.h"
#include "dibapi.h"
#include "mainfrm.h"

#ifdef _DEBUG
#undef THIS_FILE
static char BASED_CODE THIS_FILE[] = __FILE__;
#endif

#define INCEPUT_PRELUCRARI() \
	CDibDoc* pDocSrc=GetDocument();										\
	CDocTemplate* pDocTemplate=pDocSrc->GetDocTemplate();				\
	CDibDoc* pDocDest=(CDibDoc*) pDocTemplate->CreateNewDocument();		\
	BeginWaitCursor();													\
	HDIB hBmpSrc=pDocSrc->GetHDIB();									\
	HDIB hBmpDest = (HDIB)::CopyHandle((HGLOBAL)hBmpSrc);				\
	if ( hBmpDest==0 ) {												\
		pDocTemplate->RemoveDocument(pDocDest);							\
		return;															\
	}																	\
	BYTE* lpD = (BYTE*)::GlobalLock((HGLOBAL)hBmpDest);					\
	BYTE* lpS = (BYTE*)::GlobalLock((HGLOBAL)hBmpSrc);					\
	int iColors = DIBNumColors((char *)&(((LPBITMAPINFO)lpD)->bmiHeader)); \
	RGBQUAD *bmiColorsDst = ((LPBITMAPINFO)lpD)->bmiColors;	\
	RGBQUAD *bmiColorsSrc = ((LPBITMAPINFO)lpS)->bmiColors;	\
	BYTE * lpDst = (BYTE*)::FindDIBBits((LPSTR)lpD);	\
	BYTE * lpSrc = (BYTE*)::FindDIBBits((LPSTR)lpS);	\
	DWORD dwWidth  = ::DIBWidth((LPSTR)lpS);\
	DWORD dwHeight = ::DIBHeight((LPSTR)lpS);\
	DWORD w=WIDTHBYTES(dwWidth*8);	\

//---------------------------------------------------------------
CString Titlu;
#define SFARSIT_PRELUCRARI(Titlu)	\
	::GlobalUnlock((HGLOBAL)hBmpDest);								\
	::GlobalUnlock((HGLOBAL)hBmpSrc);								\
    EndWaitCursor();												\
	pDocDest->SetHDIB(hBmpDest);									\
	pDocDest->InitDIBData();										\
	pDocDest->SetTitle((LPCSTR)Titlu);									\
	CFrameWnd* pFrame=pDocTemplate->CreateNewFrame(pDocDest,NULL);	\
	pDocTemplate->InitialUpdateFrame(pFrame,pDocDest);
/////////////////////////////////////////////////////////////////////////////
// CDibView

IMPLEMENT_DYNCREATE(CDibView, CScrollView)

BEGIN_MESSAGE_MAP(CDibView, CScrollView)
	//{{AFX_MSG_MAP(CDibView)
	ON_COMMAND(ID_EDIT_COPY, OnEditCopy)
	ON_UPDATE_COMMAND_UI(ID_EDIT_COPY, OnUpdateEditCopy)
	ON_COMMAND(ID_EDIT_PASTE, OnEditPaste)
	ON_UPDATE_COMMAND_UI(ID_EDIT_PASTE, OnUpdateEditPaste)
	ON_MESSAGE(WM_DOREALIZE, OnDoRealize)
	ON_COMMAND(ID_PROCESSING_PARCURGERESIMPLA, OnProcessingParcurgereSimpla)
	ON_COMMAND(ID_PROCESSING_RANSAC, OnProcessingRansac)
	ON_COMMAND(ID_PROCESSING_BORDERTRACING, OnProcessingBordertracing)
	ON_COMMAND(ID_PROCESSING_GENERATECHAINCODES, OnProcessingGeneratechaincodes)
	ON_COMMAND(ID_PROCESSING_RECONSTRUCTFROMCHAINCODE, OnProcessingReconstructfromchaincode)
	//}}AFX_MSG_MAP

	// Standard printing commands
	ON_COMMAND(ID_FILE_PRINT, CScrollView::OnFilePrint)
	ON_COMMAND(ID_FILE_PRINT_PREVIEW, CScrollView::OnFilePrintPreview)
	ON_COMMAND(ID_PROCESSING_HOG, &CDibView::OnProcessingHog)
	ON_COMMAND(ID_PROCESSING_CLUSTERING, &CDibView::OnProcessingClustering)
END_MESSAGE_MAP()

/////////////////////////////////////////////////////////////////////////////
// CDibView construction/destruction

CDibView::CDibView()
{
}

CDibView::~CDibView()
{
}

/////////////////////////////////////////////////////////////////////////////
// CDibView drawing

void CDibView::OnDraw(CDC* pDC)
{
	CDibDoc* pDoc = GetDocument();

	HDIB hDIB = pDoc->GetHDIB();
	if (hDIB != NULL)
	{
		LPSTR lpDIB = (LPSTR) ::GlobalLock((HGLOBAL) hDIB);
		int cxDIB = (int) ::DIBWidth(lpDIB);         // Size of DIB - x
		int cyDIB = (int) ::DIBHeight(lpDIB);        // Size of DIB - y
		::GlobalUnlock((HGLOBAL) hDIB);
		CRect rcDIB;
		rcDIB.top = rcDIB.left = 0;
		rcDIB.right = cxDIB;
		rcDIB.bottom = cyDIB;
		CRect rcDest;
		if (pDC->IsPrinting())   // printer DC
		{
			// get size of printer page (in pixels)
			int cxPage = pDC->GetDeviceCaps(HORZRES);
			int cyPage = pDC->GetDeviceCaps(VERTRES);
			// get printer pixels per inch
			int cxInch = pDC->GetDeviceCaps(LOGPIXELSX);
			int cyInch = pDC->GetDeviceCaps(LOGPIXELSY);

			//
			// Best Fit case -- create a rectangle which preserves
			// the DIB's aspect ratio, and fills the page horizontally.
			//
			// The formula in the "->bottom" field below calculates the Y
			// position of the printed bitmap, based on the size of the
			// bitmap, the width of the page, and the relative size of
			// a printed pixel (cyInch / cxInch).
			//
			rcDest.top = rcDest.left = 0;
			rcDest.bottom = (int)(((double)cyDIB * cxPage * cyInch)
					/ ((double)cxDIB * cxInch));
			rcDest.right = cxPage;
		}
		else   // not printer DC
		{
			rcDest = rcDIB;
		}
		::PaintDIB(pDC->m_hDC, &rcDest, pDoc->GetHDIB(),
			&rcDIB, pDoc->GetDocPalette());
	}
}

/////////////////////////////////////////////////////////////////////////////
// CDibView printing

BOOL CDibView::OnPreparePrinting(CPrintInfo* pInfo)
{
	// default preparation
	return DoPreparePrinting(pInfo);
}

/////////////////////////////////////////////////////////////////////////////
// CDibView commands


LRESULT CDibView::OnDoRealize(WPARAM wParam, LPARAM)
{
	ASSERT(wParam != NULL);
	CDibDoc* pDoc = GetDocument();
	if (pDoc->GetHDIB() == NULL)
		return 0L;  // must be a new document

	CPalette* pPal = pDoc->GetDocPalette();
	if (pPal != NULL)
	{
		CMainFrame* pAppFrame = (CMainFrame*) AfxGetApp()->m_pMainWnd;
		ASSERT_KINDOF(CMainFrame, pAppFrame);

		CClientDC appDC(pAppFrame);
		// All views but one should be a background palette.
		// wParam contains a handle to the active view, so the SelectPalette
		// bForceBackground flag is FALSE only if wParam == m_hWnd (this view)
		CPalette* oldPalette = appDC.SelectPalette(pPal, ((HWND)wParam) != m_hWnd);

		if (oldPalette != NULL)
		{
			UINT nColorsChanged = appDC.RealizePalette();
			if (nColorsChanged > 0)
				pDoc->UpdateAllViews(NULL);
			appDC.SelectPalette(oldPalette, TRUE);
		}
		else
		{
			TRACE0("\tSelectPalette failed in CDibView::OnPaletteChanged\n");
		}
	}

	return 0L;
}

void CDibView::OnInitialUpdate()
{
	CScrollView::OnInitialUpdate();
	ASSERT(GetDocument() != NULL);

	SetScrollSizes(MM_TEXT, GetDocument()->GetDocSize());
}


void CDibView::OnActivateView(BOOL bActivate, CView* pActivateView,
					CView* pDeactiveView)
{
	CScrollView::OnActivateView(bActivate, pActivateView, pDeactiveView);

	if (bActivate)
	{
		ASSERT(pActivateView == this);
		OnDoRealize((WPARAM)m_hWnd, 0);   // same as SendMessage(WM_DOREALIZE);
	}
}

void CDibView::OnEditCopy()
{
	CDibDoc* pDoc = GetDocument();
	// Clean clipboard of contents, and copy the DIB.

	if (OpenClipboard())
	{
		BeginWaitCursor();
		EmptyClipboard();
		SetClipboardData (CF_DIB, CopyHandle((HANDLE) pDoc->GetHDIB()) );
		CloseClipboard();
		EndWaitCursor();
	}
}



void CDibView::OnUpdateEditCopy(CCmdUI* pCmdUI)
{
	pCmdUI->Enable(GetDocument()->GetHDIB() != NULL);
}


void CDibView::OnEditPaste()
{
	HDIB hNewDIB = NULL;

	if (OpenClipboard())
	{
		BeginWaitCursor();

		hNewDIB = (HDIB) CopyHandle(::GetClipboardData(CF_DIB));

		CloseClipboard();

		if (hNewDIB != NULL)
		{
			CDibDoc* pDoc = GetDocument();
			pDoc->ReplaceHDIB(hNewDIB); // and free the old DIB
			pDoc->InitDIBData();    // set up new size & palette
			pDoc->SetModifiedFlag(TRUE);

			SetScrollSizes(MM_TEXT, pDoc->GetDocSize());
			OnDoRealize((WPARAM)m_hWnd,0);  // realize the new palette
			pDoc->UpdateAllViews(NULL);
		}
		EndWaitCursor();
	}
}


void CDibView::OnUpdateEditPaste(CCmdUI* pCmdUI)
{
	pCmdUI->Enable(::IsClipboardFormatAvailable(CF_DIB));
}

void CDibView::OnProcessingParcurgereSimpla() 
{
	// TODO: Add your command handler code here
	INCEPUT_PRELUCRARI();

	
	// Makes a grayscale image by equalizing the R, G, B components from the LUT
	for (int k=0;  k < iColors ; k++)
		bmiColorsDst[k].rgbRed=bmiColorsDst[k].rgbGreen=bmiColorsDst[k].rgbBlue=k;

	
	//  Goes through the bitmap pixels and performs their negative	
	for (int i=0;i<dwHeight;i++)
		for (int j=0;j<dwWidth;j++)
		  {	
			lpDst[i*w+j]= 255 - lpSrc[i*w+j]; //makes image negative
	  }


	SFARSIT_PRELUCRARI("Operation name");
	
}

/********************************************************************************/
/********************** my code goes below **************************************/

#include <math.h>

// color constants
#define BLACK 0
#define WHITE 255

#define COLORS 256


typedef struct stPoint
{
	int x;
	int y;

	bool operator==(const struct stPoint& p);

} Point;

bool Point::operator==(const struct stPoint& p)
{
	return (this->x == p.x) && (this->y == p.y);
}


void CDibView::OnProcessingRansac()
{
	// TODO: Add your command handler code here

	INCEPUT_PRELUCRARI();

	double wd = 0.5;
	double p = 0.99;
	double s = 2.0;
	unsigned int t = 15;

	// calculate number of interations
	int k = (int)(log(1.0 - p) / log(1.0 - pow(wd, s)));
	unsigned int i, j, npt;

	Point* pt = new Point[dwHeight * dwWidth];

	// collect all black points from image
	npt = 0;
	for (i = 0; i < dwHeight; i++)
	{
		for (j = 0; j < dwWidth; j++)
		{
			if (lpSrc[i * w + j] == BLACK)
			{
				pt[npt].x = j;
				pt[npt].y = i;
				npt++;
			}
		}
	}

	// random points
	unsigned int p1, p2, maxp1, maxp2;
	unsigned int hit, max;

	max = 0;

	// find the best line k iterations
	while (k)
	{
		p1 = rand() % npt;
		p2 = rand() % npt;

		hit = 0;

		for (i = 0; i < npt; i++)
		{
			int a = (pt[p2].x - pt[p1].x);
			int b = -(pt[p2].y - pt[p1].y);
			int d = abs(a * (pt[i].y - pt[p1].y) + b *(pt[i].x - pt[p1].x))
						/ (int)sqrt(pow(a, 2.0) + pow(b, 2.0));
			if (d <= t)
			{
				hit++;
			}
		}

		// save solution
		if (hit > max)
		{
			max = hit;
			maxp1 = p1;
			maxp2 = p2;
		}

		k--;
	}

	// draw the line
	float slope = (pt[maxp2].y - pt[maxp1].y) / ((float)pt[maxp2].x - pt[maxp1].x);

	for (i = 0; i < dwHeight; i++)
	{
		int y = (int)((slope * ((int)i - pt[maxp1].x)) + pt[maxp1].y);

		if ( y >= 0  && y <= dwWidth )
		{
			lpDst[y*w+i] = BLACK;
		}
	}

	delete [] pt;

	SFARSIT_PRELUCRARI("Ransac");
}

inline unsigned int GetX(unsigned int x, unsigned char dir)
{
	unsigned new_dir;

	switch (dir)
	{
	case 1:
	case 0:
	case 7:
		new_dir = +1;
		break;
	case 2:
	case 6:
		new_dir = 0;
		break;
	case 3:
	case 4:
	case 5:
		new_dir = -1;
		break;
	}

	return x + new_dir;
}

inline unsigned int GetY(unsigned int y, unsigned char dir)
{
	unsigned new_dir;

	switch (dir)
	{
	case 1:
	case 2:
	case 3:
		new_dir = +1;
		break;
	case 0:
	case 4:
		new_dir = 0;
		break;
	case 5:
	case 6:
	case 7:
		new_dir = -1;
		break;
	}

	return y + new_dir;
}

#include <string>
#include <list>
using namespace std;

typedef struct stChainCode
{
	// staring of chain code
	Point p;
	// string of codes
	list<unsigned char> chain;

	// color
	unsigned char c;

	static void Extract(unsigned int dwHeight, 
					unsigned int dwWidth,
					unsigned int w,
					BYTE* lpSrc,
					list<struct stChainCode>& l);

	struct stChainCode& Derivate();
	bool ExtractFromFile(char* fileName);
	bool ToFile(char* fileName);

} ChainCode;

void ChainCode::Extract(unsigned int dwHeight, 
								unsigned int dwWidth, 
								unsigned int w, 
								BYTE* lpSrc,
								list<struct stChainCode>& l)
{
	unsigned int i, j;

	//Point p0;
	Point p1;
	Point pc;
	Point pt;

	bool first, finished;

	unsigned char dir, next_dir;
	unsigned char colors[COLORS];

	// clear colors vector
	memset(colors, NULL, sizeof(colors));

	ChainCode chainCode;

	for (i = 0; i < dwHeight; i++)
	{
		for (j = 0; j < dwWidth; j++)
		{
				if ((lpSrc[i*w + j] != WHITE) && (colors[lpSrc[i*w + j]] == 0) )  
				{
					chainCode.chain.clear();
					// found object pixel
					// begin border tracing
					chainCode.p.x = j;
					chainCode.p.y = i;
					chainCode.c = lpSrc[i*w + j]; // object color

					colors[chainCode.c] = 1;

					dir = 7;

					// the next pixel is first pixel
					first = true;

					finished = false;

					// init curent pixel
					pc = chainCode.p;

					// draw first pixel
					// lpDst[pc.y * w + pc.x] = p0c;

					while (!finished)
					{
						// compute next direction
						if (dir % 2 == 0)
						{
							next_dir = (dir + 7) % 8;
						}
						else
						{
							next_dir = (dir + 6) % 8;
						}

						// search for next pixel object
						// for ( ;next_dir <= 8; next_dir++)
						for (int k = 0; k < 8;  k++)
						{
							pt.x = GetX(pc.x, (next_dir + k) % 8);
							pt.y = GetY(pc.y, (next_dir + k) % 8);

							// assure that we are in image
							if (pt.y >= dwWidth || pt.y < 0)
							{
								continue;
							}

							if (pt.x >= dwHeight || pt.x < 0)
							{
								continue;
							}

							// we found pixel object on the border
							if (lpSrc[pt.y * w + pt.x] == chainCode.c)
							{
								// save second pixel
								if (first)
								{
									first = false;
									p1 = pt;
								}
								else
								{
									// if p0 equals current
									if ((chainCode.p == pc) && (p1 == pt))
									{
										finished = true;
										l.push_back(chainCode);
									}
								}

								dir = (next_dir + k) % 8;

								pc = pt;
								
								// draw border pixel in object color
								// lpDst[pc.y * w + pc.x] = p0c;
	
								// append direction
								chainCode.chain.push_back(dir);

								break;
							}
						}
					}
				}

			}
	}

}

ChainCode& ChainCode::Derivate()
{
	ChainCode result;
	
	return result;
}

#include <stdio.h>
bool ChainCode::ExtractFromFile(char* fileName)
{
	FILE* fp = fopen(fileName, "r");

	if (fp == NULL)
	{
		return false;
	}

	int x, y;

	fscanf(fp, "%d %d\n", &x, &y);

	p.x = x;
	p.y = y;

	unsigned char code;

	while( fscanf(fp, "%c", &code) != EOF )
	{
		chain.push_back(code - '0');
	}

	fclose(fp);

	return true;
}

bool ChainCode::ToFile(char* fileName)
{
	FILE* fp = fopen(fileName, "w");

	if (fp == NULL)
	{
		return false;
	}

	fprintf(fp, "%d %d\n", p.x, p.y);

	for (list<unsigned char>::iterator it = chain.begin(); it != chain.end(); it++)
	{
		char ch = *it;
		int n = fprintf(fp, "%c", ch + '0');
	}

	fclose(fp);

	return true;

}


void CDibView::OnProcessingBordertracing() 
{
	INCEPUT_PRELUCRARI();

	// clear image
	memset(lpDst, WHITE, dwHeight * w);

	list<ChainCode> l;

	ChainCode::Extract(dwHeight, dwWidth, w, lpSrc, l);

	// foreach chaincode
	for (list<ChainCode>::iterator itl = l.begin(); itl != l.end(); itl++)
	{
		ChainCode c = *itl;
		Point p = c.p;

		// draw first point
		lpDst[p.y * w + p.x] = c.c;

		for(list<unsigned char>::iterator itc = c.chain.begin(); itc != c.chain.end(); itc++)
		{
			p.x = GetX(p.x, *itc);
			p.y = GetY(p.y, *itc);

			// draw point
			lpDst[p.y * w + p.x] = c.c;
		}
	}

	SFARSIT_PRELUCRARI("Border tracing");
}

void CDibView::OnProcessingGeneratechaincodes() 
{
	// create initial variables 
	// this could go into a macro
	CDibDoc* pDocSrc=GetDocument();										
	CDocTemplate* pDocTemplate=pDocSrc->GetDocTemplate();				
	BeginWaitCursor();													
	HDIB hBmpSrc=pDocSrc->GetHDIB();									
	BYTE* lpS = (BYTE*)::GlobalLock((HGLOBAL)hBmpSrc);
	int iColors = DIBNumColors((char *)&(((LPBITMAPINFO)lpS)->bmiHeader));
	RGBQUAD *bmiColorsSrc = ((LPBITMAPINFO)lpS)->bmiColors;
	BYTE * lpSrc = (BYTE*)::FindDIBBits((LPSTR)lpS);
	DWORD dwWidth  = ::DIBWidth((LPSTR)lpS);
	DWORD dwHeight = ::DIBHeight((LPSTR)lpS);
	DWORD w=WIDTHBYTES(dwWidth*8);

	list<ChainCode> l;

	ChainCode::Extract(dwHeight, dwWidth, w, lpSrc, l);

	if (l.empty())
	{
		return;
	}

	l.front().ToFile("result.txt");


	// clean up
	::GlobalUnlock((HGLOBAL)hBmpSrc);
    EndWaitCursor();
}


void CDibView::OnProcessingReconstructfromchaincode() 
{
	// we should create new document insted of copy
	INCEPUT_PRELUCRARI();
	// clear image
	memset(lpDst, WHITE, dwHeight * w);

	ChainCode c;
	c.c = BLACK;

	if (c.ExtractFromFile("result.txt"))
	{
		Point p = c.p;

		// draw first point
		lpDst[p.y * w + p.x] = c.c;

		for(list<unsigned char>::iterator itc = c.chain.begin(); itc != c.chain.end(); itc++)
		{
			p.x = GetX(p.x, *itc);
			p.y = GetY(p.y, *itc);

			// draw point
			lpDst[p.y * w + p.x] = c.c;
		}
	}

	SFARSIT_PRELUCRARI("Reconstruct from chain code");
}

#define PI 3.14f

#include <math.h>

void hog(unsigned int x0, unsigned int y0, unsigned int x1, unsigned int y1,
			unsigned int w, BYTE* lpSrc, long hist[12])
{
	unsigned int i, j;
	int dx, dy;
	float fi;
	int u, d;
 
	memset(hist, 0, sizeof(long) * 12);

	for (i = y0 + 1; i < y1 - 1; i++)
	{
		for (j = x0 + 1; j < x1 - 1; j++)
		{
			dx = - lpSrc[i * w + j - 1] + lpSrc[i * w + j + 1];
			dy = - lpSrc[ (i + 1) * w + j ] + lpSrc[ (i - 1) * w + j];
			fi = atan2((double)dy, (double)dx);
   
			if (fi < 0)
			{
				fi += 2.0 * PI;
			}
   
			u = fi * 180.0 / PI;
			d = u / 30;
			hist[d] = hist[d] + 1;
		}
	}
}


void CDibView::OnProcessingHog()
{
	INCEPUT_PRELUCRARI();

	long hist0[12], hist1[12];
	unsigned long i, s1, s2, s3;
	
	hog(0, 0, 63, 127, w, lpSrc, hist0);
	hog(90, 0, 153, 127, w, lpSrc, hist1);
	
	s1 = 0;
	s2 = 0;
	s3 = 0;
	
	for (i = 0; i < 12; i++)
	{
		s3 += hist0[i] * hist1[i];
		s1 += hist0[i] * hist0[i];
		s2 += hist1[i] * hist1[i];
	}
	
	double cosfi = s3 / sqrt((double)s1) / sqrt((double)s2);

	SFARSIT_PRELUCRARI("HOG");
}

typedef pair<int, int> fvector;
int operator-(const fvector& v1, const fvector& v2) // distanta de la vector la vector
{
    return abs(v1.first - v2.first) + abs(v1.second - v2.second);
}

typedef struct
{
        fvector v;
        unsigned int n;
		unsigned int m;
} cluster;
typedef list<cluster> clusters_list;

cluster operator+(const cluster& c, const fvector& v) // calculam media
{
    cluster r;

    r.n = c.n + 1;
    r.v.first = (c.v.first * c.n + v.first) / r.n;
    r.v.second = (c.v.second * c.n + v.second) / r.n;
	r.m = c.m;

    return r;
}

typedef pair<fvector, short> vector_elem;
typedef list<vector_elem> vectors_list;


void CDibView::OnProcessingClustering()
{
	// TODO: Add your command handler code here

	INCEPUT_PRELUCRARI();

	// extragem vectorii
	vectors_list vl;
    for (unsigned int i = 0; i < dwHeight; i++)
    {
        for (unsigned int j = 0; j < dwWidth; j++)
        {
            if (lpSrc[i*w+j]  != 255)
            {
                fvector v;
                v.first = j;
                v.second = i;

                vector_elem ve;

                ve.first = v;
                ve.second = 0;

                vl.push_back(ve);
            }
        }
    }

    int m = 1; // current cluster number
    clusters_list cl;

	vectors_list::iterator it = vl.begin();
    // ar trebuii testat daca avem elemente in vl

    fvector& xi = (*it).first;
    (*it).second = m;
	
	// create first cluster
	cluster c;
    c.n = 1;
    c.v = xi;
	c.m = m;
	cl.push_back(c);

#define Q 10
#define THETA 70
	it++;

	// first pass
	for (; it != vl.end(); it++)
	{
		xi = (*it).first;
        
        int min = 0xFFFF;
        for (clusters_list::iterator jt = cl.begin(); jt != cl.end(); jt++)
        {
            cluster ci = *jt;
            int mint = ci.v - xi;
            if ( mint < min )
            {
                min = mint;
                // cmin = ci;
            }
        }

        // add cluster
        if ((min > THETA) && (cl.size() < Q))
        {
            m++;

			c.n = 1;
			c.v = xi;
			c.m = m;

            (*it).second = m;

            cl.push_back(c);
        }
	}

	// second pass
	for (it = vl.begin(); it != vl.end(); it++)
	{
		// check if assigned
		if ( !(*it).second )
		{
			xi = (*it).first;
			clusters_list::iterator jt = cl.begin();
			cluster* cmin = &(*jt);
			int min = cmin->v - xi;

			jt++;
			for (; jt != cl.end(); jt++)
			{
	            cluster ci = *jt;
		        int mint = ci.v - xi;
			    if ( mint < min )
				{
					min = mint;
					cmin = &(*jt);
				}
			}

			(*it).second = cmin->m;

			// adaugam la calculul mediei
			*cmin = *cmin+xi;
		}
	}

	for (it = vl.begin(); it != vl.end(); it++)
	{
		lpDst[ (*it).first.second * w + (*it).first.first ] = (*it).second;
	}


	SFARSIT_PRELUCRARI("Clustering");
}
